// Define a simple Point class for consistency with C++ code.
class Point {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
}

// Counter-Clockwise function
function ccw(a, b, c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// Check if point a is lexicographically before point b
function isLeftOf(a, b) {
    return a.x < b.x || (a.x === b.x && a.y < b.y);
}

// Length of segment (a, b)
function len(a, b) {
    return Math.sqrt((b.x - a.x) ** 2 + (b.y - a.y) ** 2);
}

// Unsigned distance of p from segment (a, b)
function dist(a, b, p) {
    return Math.abs((b.x - a.x) * (a.y - p.y) - (b.y - a.y) * (a.x - p.x)) / len(a, b);
}

// Sort points in ccw order about a pivot
function ccwSorter(pivot) {
    return function(a, b) {
        return ccw(pivot, a, b) < 0;
    }
}

// Get the index of the farthest point from segment (a, b)
function getFarthest(a, b, v) {
    let idxMax = 0;
    let distMax = dist(a, b, v[idxMax]);

    for (let i = 1; i < v.length; ++i) {
        let distCurr = dist(a, b, v[i]);
        if (distCurr > distMax) {
            idxMax = i;
            distMax = distCurr;
        }
    }

    return idxMax;
}

function giftWrapping(v) {
    v.sort(isLeftOf); // Move the leftmost point to the beginning
    let hull = [];

    do {
        hull.push(v[0]);
        let nextIndex = v.findIndex((point, index) => index > 0 && ccwSorter(v[0])(point, v[0]));
        if (nextIndex === -1) break;
        v[0] = v[nextIndex];
    } while (v[0] !== hull[0]);

    return hull;
}

function GrahamScan(v) {
    v.sort(isLeftOf); // Put leftmost point at index 0
    v = [v[0], ...v.slice(1).sort(ccwSorter(v[0]))];

    let hull = [v[0], v[1], v[2]];

    for (let i = 3; i < v.length; i++) {
        while (hull.length >= 2 && ccw(hull[hull.length - 2], hull[hull.length - 1], v[i]) >= 0) {
            hull.pop();
        }
        hull.push(v[i]);
    }

    return hull;
}


function monotoneChain(v) {
    v.sort(isLeftOf);

    let lower = [];
    for (let point of v) {
        while (lower.length >= 2 && ccw(lower[lower.length - 2], lower[lower.length - 1], point) >= 0) {
            lower.pop();
        }
        lower.push(point);
    }

    let upper = [];
    for (let point of v.slice().reverse()) {
        while (upper.length >= 2 && ccw(upper[upper.length - 2], upper[upper.length - 1], point) >= 0) {
            upper.pop();
        }
        upper.push(point);
    }

    // Concatenate lower and upper hulls; the last point of each is omitted since it's repeated
    return lower.concat(upper.slice(1, upper.length - 1));
}


function quickHull(v) {
    v = v.map(p => new Point(p[0], p[1]));
    let hull = [];

    function partitionAndHull(v, a, b, side) {
        if (v.length === 0) return;

        let idx = getFarthest(a, b, v);
        let point = v[idx];
        hull.push(point);

        // Points to the left of (a, point)
        let leftOfAPoint = v.filter(p => ccw(a, point, p) > 0);
        partitionAndHull(leftOfAPoint, a, point, true);

        // Points to the left of (point, b)
        let leftOfPointB = v.filter(p => ccw(point, b, p) > 0);
        partitionAndHull(leftOfPointB, point, b, true);
    }

    let leftMost = v.reduce((prev, curr) => isLeftOf(curr, prev) ? curr : prev, v[0]);
    let rightMost = v.reduce((prev, curr) => isLeftOf(prev, curr) ? curr : prev, v[0]);

    hull.push(leftMost);
    let left = v.filter(p => ccw(leftMost, rightMost, p) > 0);
    let right = v.filter(p => ccw(rightMost, leftMost, p) > 0);

    partitionAndHull(left, leftMost, rightMost, true);
    partitionAndHull(right, rightMost, leftMost, false);
    hull.push(rightMost);

    return hull;
}

export default { giftWrapping, GrahamScan, monotoneChain, quickHull };
